package com.aqie.medium.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 43 字符串相乘 todo
 * 1, 数组初始化
 * 2, ArrayList初始化
 * 3. 两个 char 拼接
 */
public class Multiply {
    /**
     * 1, 10ms
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0"))return "0";
        StringBuilder ans= new StringBuilder();
        int c=0;
        int i=num1.length() + num2.length()-2;
        int x=0;
        while(i>=0){
            x=c;
            for(int j=i<num1.length() ? i : (num1.length()-1);i-j<num2.length()&&j>=0;j--){
                x+=((num1.charAt(j)-'0')*(num2.charAt(i-j)-'0'));
            }
            c=x/10;
            x=x%10;
            char a = (char)('0'+x);
            ans.insert(0, a);
            i--;
        }
        if(c!=0) ans.insert(0,(char)(c+'0'));
        return ans.toString();
    }
    /** 2, 30ms
    m 位数和n位数相乘，结果位数为m+n-1或m + n，因此存进位数据数组大小申请为m+n位
    对应位相乘后的结果与进位数据数组对应位置相加，十位数存入进位数组下一位，个位数留在该位
    存进位数据数组在转为字符串返回的时候，要把前导零去掉

     */
    public static String multiply2(String num1, String num2) {
        int n = num1.length(), m = num2.length(), p = 0;

        Integer[] arr = new Integer[n+m];
        Arrays.fill(arr, 0);
        List<Integer> bits = Arrays.asList(arr);
        for (int i = m - 1; i >= 0; --i) {
            p = m - 1 - i;
            for (int j = n - 1; j >= 0; --j) {
                int res = (num2.charAt(i) - '0') * (num1.charAt(j) - '0') + bits.get(p);
                if (res >= 10)
                    bits.set(p + 1, bits.get(p+1) + res/10);
                bits.set(p, (res % 10));
                p++;
            }
        }
        StringBuilder ans = new StringBuilder();
        int terminal = m + n - 1;
        while (terminal >= 0 && bits.get(terminal) == 0)
            terminal--;
        for (int i = 0; i <= terminal; ++i) {
            ans.insert(0, (char) (bits.get(i) + '0'));
        }
        return ans.toString().equals("") ? "0" : ans.toString();
    }

    public static void main(String[] args) {
        String num1 = "2", num2 = "31";
        // num1 = "3"; num2 = "12";
        num1 = "9"; num2 = "9";
        // num1 = "123"; num2 = "456";  // 56088
        num1 = "98541321231234556489103612315646564612315642185645235642313123";
        num2 = "9852421245545445623128994894564531231561321516548754464456464";
        System.out.println(multiply(num1, num2));


    }

}
